//
//  XBHeapExample.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/23.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBHeapExample.h"

// -- 堆是完全二叉树最典型的应用。最大堆，完全二叉树的所有的父节点都比子节点大。反之为最小堆。这里可以用二叉树的性质来建立堆。用二叉树的性质来描述父子节点的关系。也可以使用包含左右子树只针对结构表示节点和节点之间的关系。
//这里用了二叉树的性质，感觉更直观一点


DATATYPE arr[] = {99,5,36,7,22,17,92,12,2,19,25,28,1,46};

int max =14;
//存放堆节点的数组
DATATYPE heapArr[MAX_SIZE];
//在一个完全二叉树中调整节点的位置
void setNodeP(int curIdx,int maxNode)
{
    if (curIdx*2>maxNode) {
        return;
    }
    int t=curIdx;
    //和左子树比较节点大小
    if (heapArr[curIdx]>heapArr[curIdx*2]) {
        
        //向下调整
        t = curIdx*2;
    }
    if (curIdx*2+1<=maxNode) {
        
        if (heapArr[t]>heapArr[curIdx*2+1]) {
            t =curIdx*2+1;
        }
    }
    if (t!=curIdx) {
        
        int tem = heapArr[curIdx];
        heapArr[curIdx] = heapArr[t];
        heapArr[t]=tem;
        setNodeP(t,maxNode);
    }
    
}

void swap(int x,int y)
{
    int t;
    t =heapArr[x];
    heapArr[x]=heapArr[y];
    heapArr[y]=t;
    return;
}


//void setNodeP2(int idx,int max)
//{
//    
//    int flag =0;
//    int t;
//    while (idx*2<=max&&flag==0) {
//        
//        if (heapArr[idx]>heapArr[idx*2]) {
//            
//            t = idx*2;
//        }
//        else{
//            t=idx;
//        }
//        if (idx*2+1<=max) {
//            
//            if (heapArr[idx]>heapArr[idx*2+1]) {
//                t = idx*2+1;
//            }
//        }
//        if (idx!=t) {
//            
//            int tem = heapArr[idx];
//            heapArr[idx]=heapArr[t];
//            heapArr[t]=tem;
//            idx = t;
//        }
//        else
//        {
//            flag =1;
//        }
//    }
//}

void siftdown(int i)
{
    int t,flag =0;
    while (i*2<=max && flag==0) {
        
        if (heapArr[i]>heapArr[2*i]) {
            
            t = i*2;
        }
        else
        {
            t=i;
        }
        if (i*2+1<=max) {
            
            if (heapArr[t]>heapArr[i*2+1]) {
                t=i*2+1;
            }
        }
        if (t!=i) {
            
            swap(t, i);
            i=t;
        }
        else
        {
            flag =1;
        }
    }
    
    
}

int deletemax()
{
    int t;
    t=heapArr[1];
    heapArr[1]=heapArr[max];
    max--;
    //siftdown(1);//(1, max);
    setNodeP(1, max);
    return  t;
    
}
//根据一个数组建立堆
void createXBHeap()
{
    int sum = sizeof(arr)/sizeof(int);
    //1.构建完全二叉树
    for (int i =1; i<=sum; i++) {
        
        heapArr[i] = arr[i-1];//根据原始数组里面的数据，构建一个完全二叉树,完全二叉树的节点从1开始，方便计算
    }
    //2.调整所有的子树使得符合最小堆的特性,从最后一个非叶子节点开始找就行，下标是sum/2
   // DATATYPE t;
    for (int idx = max /2; idx >=1; idx --) {
        
        setNodeP(idx, max);
    }
    //这里就是堆排序
    for (int i =1; i<=sum; i++) {
        printf("%d ",deletemax());
    }
}












